#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <climits>


using namespace std;

class Solution {
    vector<vector<int> > fgs;
    vector<int> X={1,-1,0,0};
    vector<int> Y={0,0,1,-1};
    int lenr,lenc,wordlen;
public:
    bool helper(vector<vector<char>>& board,int idx,int jdx,string word,int index){
        if(idx<0||jdx<0||idx>=lenr||jdx>=lenc||fgs[idx][jdx]||board[idx][jdx]!=word[index]){
            return false;
        }
        // cout << "idx= "<< idx << " jdx= "<< jdx << " board[idx][jdx]= "<<board[idx][jdx]<< " index= "<< index << "word[index]= "<< word[index]<<endl; 
        fgs[idx][jdx]=1;
        if(index==wordlen-1){
            return true;
        }else{
            for(int i=0;i<4;i++){
                int new_i=idx+X[i],new_j=jdx+Y[i];
                bool ans=helper(board,new_i,new_j,word,index+1);
                if(ans) return ans;
            }
        }
        fgs[idx][jdx]=0;
        return false;
    }
    bool exist(vector<vector<char>>& board, string word) {
        lenr=board.size(),lenc=board[0].size(),wordlen=word.size();
        fgs=vector<vector<int> >(lenr,vector<int>(lenc,0));
        for(int i=0;i<lenr;i++){
            for(int j=0;j<lenc;j++){
                if(board[i][j]==word[0]){
                    bool ans=helper(board,i,j,word,0);
                    if(ans) return ans;
                }
            }
        }
        return false;
    }
};

int main(){
    vector<vector<char> > v={{'A','B','C','E'},{'S','F','C','S'},{'A','D','E','E'}};
    string word="ABCCZD";
    Solution s;
    cout << s.exist(v,word)<<endl;



    return 0;
}